This specification relates to generating query refinements from user preference data. Internet search engines provide information about Internet accessible resources (e.g., Web pages, images, text documents, multimedia content) that are responsive to a user's search query by returning a set of search results in response to the query. A search result includes, for example, a Uniform Resource Locator (URL) and a snippet of information for resources responsive to a query. However, the set of search results that are presented to a user are not always what the user is trying to find. A search engine may present query refinements (e.g., other queries related to the user's search query) to the user to help the user find desired search results.